package 二分.二分答案;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/6 10:56
 */
public class leetcode875爱吃香蕉的珂珂 {


    /*
     按照 二分 答案的 套路:
     1. 答案的 范围 : 1  ~  10 ^ 9
     2.  存在 关联的 单调性, 当 mid 满足 的时候 ,那么 mid 右边的答案全都 满足!
     3. 答案  + 条件 -----> 限制 (这里的  限制 就是 规定的 时间)
     4. 数据量, 其他方法的 时间复杂度 明显 不能解决 该数据量
     */


    public int solution(int piles[],int limitTime){
        int left = 1,right = 1000000000;
        while(left < right){
            int mid = left + right >> 1;
            if(check(mid,piles) > limitTime){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        return left;
    }
    /*
     给出 一个 speed : mid 和 香蕉 数组 piles
     返回 能够 吃完 的时间:

     这里的 一个 技巧: 向上取整的 技巧:
     a/b 向上 取整 =  (a + b - 1) / b
     可以 分 类 讨论一下 : 就明白 正确性了:
     a > b
     a % b == 0
     a < b
     上面的 三种情况!
     */
    private int check(int mid, int[] piles) {
        int sumTime = 0;
        for(int num : piles){
            sumTime += (num + mid - 1) / mid;
        }
        return sumTime;
    }


}
